package com.atguigui.leetcode;

/**
 * 854.相似度为 K 的字符串
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/9/21 8:38
 */
public class P854KSimilarStrings {
    public static void main(String[] args) {
        Solution solution = new P854KSimilarStrings().new Solution();
        // TO TEST
    }

    class Solution {
        public int kSimilarity(String s1, String s2) {
            /*int n = s1.length();
            Queue<Pair<String, Integer>> queue = new ArrayDeque<Pair<String, Integer>>();
            //判断已经遍历过的字符
            Set<String> visit = new HashSet<String>();
            queue.offer(new Pair<String, Integer>(s1, 0));
            visit.add(s1);
            //最小k值
            int step = 0;
            while (!queue.isEmpty()) {
                int sz = queue.size();
                for (int i = 0; i < sz; i++) {
                    Pair<String, Integer> pair = queue.poll();
                    String cur = pair.getKey();
                    int pos = pair.getValue();
                    //判断两个字符是否相等
                    if (cur.equals(s2)) {
                        return step;
                    }
                    //判断两个同位字母是否相等
                    while (pos < n && cur.charAt(pos) == s2.charAt(pos)) {
                        pos++;
                    }
                    for (int j = pos + 1; j < n; j++) {
                        if (s2.charAt(j) == cur.charAt(j)) {
                            continue;
                        }
                        if (s2.charAt(pos) == cur.charAt(j)) {
                            //交换
                            String next = swap(cur, pos, j);
                            if (!visit.contains(next)) {
                                visit.add(next);
                                queue.offer(new Pair<String, Integer>(next, pos + 1));
                            }
                        }
                    }


                }
                step++;
            }*/

            return 0;
        }

        public String swap(String cur, int i, int j) {
            char[] arr = cur.toCharArray();
            char c = arr[i];
            arr[i] = arr[j];
            arr[j] = c;
            return new String(arr);
        }

    }
}
